package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/21 21:36
 */
public class C174 {


    public static int calculateMinimumHP(int[][] dungeon) {
        int R = dungeon.length, C = dungeon[0].length;
        int[][] dp = new int[R][C];     // 消耗最少
        int[][] minHp = new int[R][C];  // 消耗最少到这里的hp
        dp[0][0] = dungeon[0][0] > 0 ? 1 : Math.abs(dungeon[0][0]) + 1;
        minHp[0][0] = dungeon[0][0] > 0 ? dungeon[0][0] + 1 : 1;
        // 第一行
        for (int c = 1; c < C; c++) {
            int hp = minHp[0][c - 1] + dungeon[0][c];
            if (hp > 0) {
                dp[0][c] = dp[0][c - 1];
                minHp[0][c] = hp;
            } else {
                dp[0][c] = dp[0][c - 1] + Math.abs(hp) + 1;
                minHp[0][c] = 1;
            }
        }
        // 第一列
        for (int r = 1; r < R; r++) {
            int hp = minHp[r - 1][0] + dungeon[r][0];
            if (hp > 0) {
                dp[r][0] = dp[r - 1][0];
                minHp[r][0] = hp;
            } else {
                dp[r][0] = dp[r - 1][0] + Math.abs(hp) + 1;
                minHp[r][0] = 1;
            }
        }
        // 从上往下(外层)从左往右(内层) 依赖于左边上边最大的值
        for (int r = 1; r < R; r++) {
            for (int c = 1; c < C; c++) {
                int lhp = minHp[r][c - 1] + dungeon[r][c];
                int thp = minHp[r - 1][c] + dungeon[r][c];
                int lNeed = (lhp > 0 ? 0 : Math.abs(lhp) + 1) + dp[r][c - 1];
                int tNeed = (thp > 0 ? 0 : Math.abs(thp) + 1) + dp[r - 1][c];
                if (lNeed <= tNeed) {
                    minHp[r][c] = lhp > 0 ? lhp : 1;
                    dp[r][c] = lNeed;
                } else {
                    minHp[r][c] = thp > 0 ? thp : 1;
                    dp[r][c] = tNeed;
                }
            }
        }
        for (int[] nums : minHp) {
            System.out.println(Arrays.toString(nums));
        }
        System.out.println("==========");
        for (int[] nums : dp) {
            System.out.println(Arrays.toString(nums));
        }
        return dp[R - 1][C - 1];
    }


    // for test
    public static void main(String[] args) {
        /*int[][] dungeon = {
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5}
        };*/
        /*int[][] dungeon = {
                {3, -20, 30},
                {-3, 4 , 0}
        };*/
        int[][] dungeon = {
                {1, -3, 3},
                {0, -2, 0},
                {-3, -3, -3}
        };
        System.out.println(calculateMinimumHP(dungeon));
    }

}
